package mo.offer_special;

import mo.common.ListNode;

public class L023 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int l1 = 0;
        ListNode tmp = headA;
        while (tmp != null) {
            l1++;
            tmp = tmp.next;
        }
        int l2 = 0;
        tmp = headB;
        while (tmp != null) {
            l2++;
            tmp = tmp.next;
        }

        int gap = l1 - l2;
        while (gap != 0) {
            if (gap < 0) {
                headB = headB.next;
                gap++;
            } else {
                headA = headA.next;
                gap--;
            }
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

}
